package dp;

public class ds647 {
    public static void main(String[] args) {
        System.out.println(countSubstrings2("abc"));
    }
    public static int countSubstrings(String s) {
        char[] ch = s.toCharArray();
        int n = s.length();
        int sum = ch.length;
        for (int i = 0; i < n; i++) {
            int b = i - 1, e = i + 1;
            while(b >= 0 && e < n){
                if(ch[b] == ch[e]){
                    sum++;
                    b--;
                    e++;
                }
                else break;
            }
        }
        for (int i = 0; i < n; i++) {
            int b = i, e = i + 1;
            while(b >= 0 && e < n){
                if(ch[b] == ch[e]){
                    sum++;
                    b--;
                    e++;
                }
                else break;
            }
        }
        return sum;
    }


    public static int countSubstrings2(String s) {
        char[] ch = s.toCharArray();
        int n = s.length();
        int sum = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i ; j < n; j++) {
                if(ch[i] == ch[j]){
                    if(j - i <= 1){
                        dp[i][j] = true;
                        sum++;
                    }
                    else if(dp[i + 1][j - 1]){
                        dp[i][j] = true;
                        sum++;
                    }
                }
            }
        }
        return sum;
    }
}
